问题

If it is overflow, return MAX_INT.

思路

这道题难在不能使用乘除取余操作，所以我们只能手动的实现除法，我们来看看如何实现。

我们假设被除数为，除数为d

首先，本能想到10 = 2*5 ，10/2 = 5，说明10中有5个2，这里可以用循环来做，看D中间有多少个d就行了。

现在有另一个问题，正负数怎么办？我们知道，除法里，异号为负，同号为正，既然不能使用乘除判断，那我们就只能写个判断，这个flag到时候就充当标志。

  1.  boolean flag = (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0);

当然还有更好的实现方式，既然不能用乘除，可以用位运算呀，这和异或操作的含义刚好一样。

然后，把D和d同时取绝对值就好了。

  1.      long did = Math.abs((long)dividend);
  2.      long dis = Math.abs((long)divisor);

注意：这里除数一定要用long，因为如果最小值取绝对值会溢出

好了，我们可以测试下代码。发现超时，想想也是，上面的循环太慢了。其实我们稍微想一下就可以提速，我们可以采用逐渐逼近的思路：

  • 我们先看i = N个d可不可以
  • 如果可以，我们看看i = 2N个d可以不可以
    • 如果还可以就继续看i = 4N个d可以不可以
      • 直到不可以减，我们让减去i个d

这里为什么使用2的倍数，因为可以用位运算呀~~

  1. d << 2 就相当与d*4

我们再用一个i来就记数 i = 0 开始

这里我们用一个临时变量mul_d存d的左移操作，注意：mul_d必须为long，因为左移操作很可能溢出！！

  1. public class Solution {
  2.     public int divide(int dividend, int divisor) {
  3.         if(divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1))
  4.             return Integer.MAX_VALUE;
  5.         int i,total = 0;
  6.         //判断正负号
  7.         boolean sign = ((dividend < 0) ^ (divisor < 0));
  8.         //这里必须要long,因为如果最小值取绝对值会溢出
  9.         long did = Math.abs((long)dividend);
  11.         while(did >= dis)
  12.         {
  13.             i = 0;
  14.             //每次左移乘2，记录下来，直到不能减
  15.             while(did >= (mul_dis<<1)) 
  16.             {
  17.                 i++;
  18.                 mul_dis <<= 1;
  19.             }
  20.             did -= mul_dis;
  21.             total += 1<<i;
  22.         }
  23.         //根据符号返回
  24.         return sign?-total:total;